/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/3sum
   @Language: C++
   @Datetime: 19-05-22 17:28
   */

class Solution {
public:
	vector<vector<int> > threeSum(vector<int>& nums) {
		sort(nums.begin(),nums.end());
		vector<vector<int> > vs;
		for(int i=0; i<nums.size(); ++i){
			if(i>0 && nums[i-1]==nums[i]) continue;
			for(int j=i+1, k=nums.size()-1; j<k;){
				if(j>i+1 && nums[j-1]==nums[j]) {
					++j;
					continue;
				}
				if(k<nums.size()-1 && nums[k]==nums[k+1]){
					--k;
					continue;
				}
				const int sum=nums[i]+nums[j]+nums[k];
				if(sum>0) --k;
				else if(sum<0) ++j;
				else vs.push_back({nums[i],nums[j++],nums[k--]});
			}
		}
		return vs;
	}
};
